A database management system (DBMS) is computer software designed for the purpose of managing a database. A DBMS processes queries which represent requests for information. One of the popular DBMS is a relational DBMS (RDBMS) and queries to an RDBMS are described in SQL (Structured Query Language) (refer to “Oracle Database Performance Tuning Guide”, 10 g Release 1 (10.1), Part Number: B12449-01).
A table in an RDBMS includes a plurality of records. A record is composed of columns. TBL in FIG. 1 is a table including 10,000 records. Each record includes three columns, “ID”, “PRODUCT NAME”, and “PRICE”.
A query includes an “access type” indicating how to manipulate records, a “target” indicating which columns of a record should be manipulated, a “scope” indicating which part of data, or which table, records are included in, and a “condition” indicating conditions which selected records must satisfy. Then, “target” in selected record are manipulated according to “access type”. The “access type” is “select (data reading)”, “update (data update)”, “insert (record insertion)”, or “delete (record deletion)” in SQL. The query in FIG. 1 specifies “read all columns of records whose value of price is between 500 and 1000 (a target “*” implies all columns) from the table TBL”. This query reads three records which satisfies a condition.
A table is stored into blocks. A block is a sequence of bytes or bits having nominal length (block size), and can store records according to a block size and record sizes. We call blocks storing a table “table blocks”.
Metadata, typically a tree index, is often added to a column of a table in order to find records whose value of the column satisfies given conditions without checking all records in a table. A tree index includes “entries” which are composed of a key value and a pointer. One entry corresponds to one record. A key value is a value of a column of a corresponding record. A pointer shows which table block the corresponding record is stored. Entries are also stored into blocks, which we call leaf blocks, and are sorted by key value. A tree index also includes “branches”. A branch includes pointers to leaf blocks and ranges of key values of entries in the leaf blocks. We call a block storing branches a “branch block”. A branch can include a pointer to a branch block and a range of key values in branch blocks. Then, we can find records which a query manipulates by following pointers in a tree index.
As shown in FIG. 2, the leaf block has a plurality of entries, and each entry is composed of a key value and a pointer. In this example, the key value is “PRICE”. In each leaf block, the plurality of entries is sorted by key value.
When the metadata can be used, the DBMS refers to the metadata and consequently accesses the table block. That is, the DBMS refers to the metadata and obtains pointers P3, P4 and P5 correlated to the key values of selected records and then accesses the addresses indicated by the pointers P3, P4 and P5. In this case, the DBMS is required to access a total of five blocks (the branch block, the leaf block and the table blocks BL-i, BL-j and BL-k).
As mentioned above, the DBMS accesses the necessary blocks which store data which need accessed for processing a query. Hereafter, an access to a block is referred to as a block access. Also, hereafter, the number of the block accesses necessary for a query process is referred to as a block access number. Also, hereafter, the data reading from the block necessary for the query process is referred to as a fetch.
A load by fetching greatly depends on the block access number, namely, the content of the query. For example, when the query manipulates a large number of records, many blocks must be accessed, which increases the load by fetching. A Load by fetching has a considerable influence on the processing performance of the computer system. Therefore, it is important to conserve a load by fetching, namely, the block access number to a suitable value.
As the typical technique related to the database management system (DBMS), the followings are known.
Japanese Laid-Open Patent Application JP-A-Heisei, 9-97200 discloses a database system of a client-server architecture. A server has a log file for processing histories of queries. The server refers to the log file when the server receives a query from a client. Then, the server estimates a load of the query from processing histories of a similar query and sends the estimation to the client. The client determines whether the query should be really executed based on the estimation or not.
We have now discovered that it is important to conserve a load by fetching, namely, the block access number to the suitable value from the viewpoint of the processing performance of the computer system as mentioned above. Thus, the technique that can estimate the block access number (the number of block accesses) is desired.